#include "Sort.h"

// 直接插入排序
// 基本思想就是摸牌的过程, 有一个有序区间, 插入一个数据后依旧保持它有序
// [0, end]有序, end+1位置的值插入[0, end], 让[0, end+1]依旧有序
void InsertSort(int *a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = 0;
        int tmp = a[end + 1];
        // 保证牌是有序的
        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + 1] = a[end]; // 往后挪
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}


// 希尔排序 - 直接插入排序上的优化
// 先预排序让数组接近有序, 最后直接插入排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while(gap > 1) // gap>1时都是预排序, 接近有序, gap==1时是直接插入排序
    {
        gap /= 2; // 一定要保证最后一次gap==1, 所以gap = gap / 3 + 1也行

        for(int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while(end >= 0)
            {
                if(a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}


// 堆排序
// 排升序-建大堆
void AdjustDown(int* a, int size, int root)
{
    int parent = root;
    int child = root * 2 + 1; // 默认是左孩子
    while(child < size) // 调到叶子就终止了
    {
        if(child + 1 < size && a[child + 1] > a[child])
        {
            child++;
        }

        if(a[child] > a[parent])
        {
            std::swap(a[child], a[parent]);
            // 继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    // 从第一个非叶子结点开始向下调整
    for(int i = (n - 1 - 1) / 2; i >= 0; i--) // 建大堆 - 堆顶是最大的值
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while(end > 0)
    {
        std::swap(a[0], a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}



// 冒泡排序
void BubbleSort(int* a, int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = 0; j < n - i - 1; j++)
        {
            if(a[j] > a[j + 1])
            {
                std::swap(a[j], a[j+1]);
            }
        }
    }
}


// 快速排序
void QuickSort(int* a, int n)
{
    
}